package huawei;

import java.util.ArrayList;

/**
 * 智能驾驶
 */
public class Q104 {

    static int[][] map = {{10,20}, {30,40}};
//    static int[][] map = {{10,30,30,20}, {30,30,-1,10},{0,20,20,40}, {10,-1,30,40}};
//    static int[][] map = {{10,0,30,-1,10}, {30,0,20,0,20},{10,0,10,0,30}, {10,-1,30,0,10}};
//    static int[][] map = {{10,30,30,20}, {30,30,20,10},{10,20,10,40}, {10,20,30,40}};

    static boolean[][] visited = new boolean[map.length][map[0].length];

    static int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    static int minFistGas = Integer.MAX_VALUE; // 计算第一次加油的最小值

    public static void main(String[] args) {
         if (dfs(0, 0,0, 0,false)) {
             System.out.println(minFistGas);
         } else {
             System.out.println(-1);
         }
    }

    public static boolean dfs(int x, int y, int needGas,int fistNeedGas, boolean isAddGas ) {
        if ((x == map.length && y == map[0].length - 1) || (x == map.length - 1 && y == map[0].length)) {
            if (isAddGas) {
                minFistGas = Math.min(minFistGas, fistNeedGas);
            } else {
                minFistGas = Math.min(minFistGas, needGas);
            }
            return true;
        }
        // 未超出边界并且没有经过并且不是障碍物且需要的(汽油小于等于油箱容量100或是加油站)
        if (!(x >= 0 && x < map.length && y >= 0 && y < map[0].length && !visited[x][y] && map[x][y] != 0 && (needGas <= 100 || map[x][y] == -1))) {
            return false;
        }

        // 加油站
        if (map[x][y] == -1) {
            if (!isAddGas){
                // 如果没有加过油
                fistNeedGas = needGas;
            }
            isAddGas = true;
            needGas = 0;
        } else {
            needGas += map[x][y];
        }

        // 标记走过
        visited[x][y] = true;
        boolean canOver = false; // 是否可以走通
        for (int[] d : direction) {
             if (dfs(x + d[0], y + d[1], needGas, fistNeedGas, isAddGas)) {
                 canOver = true; // 东南西北只要有一条走通就行
             }
        }
        // 回溯
        visited[x][y] = false;
        return canOver;
    }
}
